By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 8, Issue 4, pp. 479-656

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

Optimal and Near-Optimal Scheduling Algorithms for Batched Processing in Linear Storage

J. R. Bitner and C. K. Wong

pp. 479-498

BibTeX  Abstract Full Text:  PDF

Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix

Ravindran Kannan and Achim Bachem

pp. 499-507

BibTeX  Abstract Full Text:  PDF

Towards a Precise Characterization of the Complexity of Universal and Nonuniversal Turing Machines

Lutz Priese

pp. 508-523

BibTeX  Abstract Full Text:  PDF

On $V$-Optimal Trees

A. Bagchi and J. K. Roy

pp. 524-541

BibTeX  Abstract Full Text:  PDF

A Note on Locating a Set of Points in a Planar Subdivision

F. P. Preparata

pp. 542-545

BibTeX  Abstract Full Text:  PDF

On the Semantics of "Data Type"

James Donahue

pp. 546-560

BibTeX  Abstract Full Text:  PDF

A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem

Richard M. Karp

pp. 561-573

BibTeX  Abstract Full Text:  PDF

Classes of Pebble Games and Complete Problems

Takumi Kasai, Akeo Adachi, and Shigeki Iwata

pp. 574-586

BibTeX  Abstract Full Text:  PDF

Translatability and Decidability Questions for Restricted Classes of Program Schemas

Elaine J. Weyuker

pp. 587-598

BibTeX  Abstract Full Text:  PDF

An Efficient Method for Storing Ancestor Information in Trees

David Maier

pp. 599-618

BibTeX  Abstract Full Text:  PDF

Node-Deletion NP-Complete Problems

M. S. Krishnamoorthy and Narsingh Deo

pp. 619-625

BibTeX  Abstract Full Text:  PDF

A Family of Algorithms for Powering Sparse Polynomials

David K. Probst and Vangalur S. Alagar

pp. 626-644

BibTeX  Abstract Full Text:  PDF

A Linear Time Algorithm for Finding Minimum Cutsets in Reducible Graphs

Adi Shamir

pp. 645-655

BibTeX  Abstract Full Text:  PDF

Corrigenda: A Completeness Criterion for Spectra

T. Hikita and A. Nozaki

p. 656

BibTeX  Abstract Full Text:  PDF